package leetcode.weekly.week308;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

//Solution4Test
public class Solution4 {

	public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
//    	k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
		int[][] pos = new int[k + 1][2];
		boolean row = this.find(pos, k, rowConditions, 0);
		boolean col = this.find(pos, k, colConditions, 1);
		if (!row || !col) {
			return new int[][] {};
		}
		int[][] ans = new int[k][k];
		for (int i = 1; i < pos.length; i++) {
			int[] p = pos[i];
			if (p[0] - 1 < 0 || p[1] - 1 < 0) {
				return new int[][] {};
			}
			ans[p[0] - 1][p[1] - 1] = i;
		}
		return ans;
	}

	private boolean find(int[][] pos, int k, int[][] rowConditions, int index) {
		int[] inrows = new int[k + 1];
		Map<Integer, List<Integer>> edges1 = new HashMap<>();
		for (int i = 1; i <= k; i++) {
			edges1.put(i, new ArrayList<>());
		}
		for (int i = 0; i < rowConditions.length; i++) {
			int[] row = rowConditions[i];
			inrows[row[1]]++;
			edges1.get(row[0]).add(row[1]);
		}
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 1; i < inrows.length; i++) {
			int r = inrows[i];
			if (r == 0) {
				queue.add(i);
			}
		}
		if (queue.isEmpty()) {
			return false;
		}
		int r = 1;
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			if (pos[cur][index] != 0) {
				return false;
			}
			pos[cur][index] = r++;
			List<Integer> nexts = edges1.get(cur);
			for (int next : nexts) {
				inrows[next]--;
				if (inrows[next] == 0) {
					queue.add(next);
				}
			}
		}
		return true;
	}
}
